package LeetCode刷题;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-10-18 16:56
 * @description: Functions of this class is
 * 民间解法（单调队列）：
 * 遍历数组，将 数 存放在双向队列中，并用 L,R 来标记窗口的左边界和右边界。
 * 队列中保存的并不是真的 数，而是该数值对应的数组下标位置，并且数组中的数要从大到小排序。
 * 如果当前遍历的数比队尾的值大，则需要弹出队尾值，直到队列重新满足从大到小的要求。
 * 刚开始遍历时，L 和 R 都为 0，有一个形成窗口的过程，此过程没有最大值，L 不动，R 向右移。
 * 当窗口大小形成时，L 和 R 一起向右移，每次移动时，判断队首的值的数组下标是否在 [L,R] 中，如果不在则需要弹出队首的值，当前窗口的最大值即为队首的数。
 * class Solution {
 *     public int[] maxSlidingWindow(int[] nums, int k) {
 *         int len=nums.length;
 *         if(len<2||nums==null){
 *             return nums;
 *         }
 *         LinkedList<Integer> queue=new LinkedList();//用于存入当前元素的下标，来进行判断当前元素是否在窗口中
 *         int ans[]=new int[len-k+1];//一共有n-k+1个窗口
 *
 *          //牢记队列默认的规则：Last进！！！！First出！！！！！
 *
 *         for(int i=0;i<len;i++){
 *             //维护一个队列，每次新添加的元素如果开始逐一遍历，要保持从大到小的顺序来进行存放
 *             while(!queue.isEmpty()&&nums[queue.peekLast()]<=nums[i]){
 *                 queue.pollLast();//如果当前队头最大的元素都比当前数组中元素小的话
 *                 //对队列进行循环判断
 *             }
 *             //直到队头元素小于当前数组中的元素
 *             queue.addLast(i);//把当前数组元素的索引下标入队尾
 *
 *             if(queue.peekFirst()<=i-k){//判断当前队头最大的元素是否在窗口中
 *                 queue.pollFirst();
 *             }
 *             if(i>=k-1){
 *                 //如果当前元素的下标开始>=k时，说明可以开始添加答案元素了
 *                 //然后根据这个下标来进行添加元素
 *                 ans[i-k+1]=nums[queue.peekFirst()];
 *             }
 *         }
 *         return ans;
 *     }
 * }
 *
 **/
public class NoNo双向队列滑动窗口 {
    public static void main(String args[]){
        LinkedList<Integer> list=new LinkedList<>();

    }

}